Số nguyên tố là
số tự nhiên lớn hơn 1 không phải là
tích của hai số tự nhiên nhỏ hơn. Nói cách khác, số nguyên tố là những số chỉ có đúng hai
ước số là 1 và chính nó. Các số tự nhiên lớn hơn 1 không phải là số nguyên tố được gọi là
hợp số. Chẳng hạn, 5 là số nguyên tố bởi vì cách duy nhất để viết nó dưới dạng một
tích, 1 × 5 hoặc 5 × 1, có một thừa số là chính số 5. Tuy nhiên, 4 là hợp số vì nó là tích của hai số (2 × 2) mà cả hai số đều nhỏ hơn 4. Số nguyên tố là nội dung trọng tâm trong
lý thuyết số theo
định lý cơ bản của số học: mọi số tự nhiên lớn hơn 1 hoặc là số nguyên tố hoặc có thể được
phân tích ra thừa số nguyên tố một cách duy nhất
xê xích một phép hoán vị.Tính chất của một số nguyên tố được gọi là
tính nguyên tố. Một phương pháp đơn giản để kiểm tra tính nguyên tố của một số n {\displaystyle n} , được gọi là
giải thuật chia thử, kiểm tra xem n {\displaystyle n} có phải là bội số của bất kỳ số nguyên nào giữa 2 và n {\displaystyle {\sqrt {n}}} hay không. Một số thuật toán khác bao gồm
phép kiểm tra Miller–Rabin, tuy nhanh nhưng có xác suất nhỏ cho kết quả sai và
phép kiểm tra tính nguyên tố AKS, vốn luôn cho lời giải đúng trong khoảng
thời gian đa thức nhưng quá chậm để áp dụng trong thực tế. Ngoài ra, còn có một số thuật toán nhanh dành cho các số có dạng đặc biệt, chẳng hạn như
số nguyên tố Mersenne. Tính đến tháng 9 năm 2020, số nguyên tố lớn nhất đã biết có 24.862.048 chữ số, được khám phá vào tháng 12 năm 2018.
[1]Có
vô số số nguyên tố, như đã
được Euclid chứng minh vào khoảng năm 300 TCN. Hầu như không có công thức đơn giản nào để phân biệt số nguyên tố và hợp số. Tuy nhiên, sự phân phối các số nguyên tố trong tập hợp các số tự nhiên có trong một khoảng giá trị lớn có thể được mô hình hóa theo thống kê. Kết quả đầu tiên theo hướng đó là
định lý số nguyên tố, được chứng minh vào cuối thế kỷ 19, cho rằng
xác suất để một số bất kỳ là số nguyên tố
tỉ lệ nghịch với số chữ số của nó, nghĩa là với
logarit của nó.Một số bài toán lịch sử liên quan đến số nguyên tố vẫn chưa có lời giải. Chúng bao gồm
giả thuyết Goldbach, cho rằng mọi số nguyên chẵn lớn hơn 2 có thể được biểu diễn thành tổng của hai số nguyên tố, và phỏng đoán về số
nguyên tố sinh đôi, cho rằng có vô số cặp số nguyên tố chỉ có một số chẵn giữa chúng. Những bài toán như thế đã góp phần thúc đẩy sự phát triển của nhiều nhánh trong lý thuyết số tập trung vào khía cạnh
đại số và
giải tích của các số. Số nguyên tố cũng có ứng dụng trong một số lĩnh vực của
công nghệ thông tin, chẳng hạn như
mật mã hóa khóa công khai, dựa vào sự phức tạp trong việc
phân tích các số nguyên lớn ra thừa số nguyên tố. Trong
đại số trừu tượng, còn có một số đối tượng khác có đặc điểm và tính chất giống với số nguyên tố, trong đó gồm
phần tử nguyên tố và
i-đê-an nguyên tố.